6965. Спасение Энтерпрайза

Звездолет Энтерпрайз окружен Клингонами! Найдите самый быстрый путь эвакуации и выведите его время.

На вход подается прямоугольная сетка, каждая ячейка которой содержит либо Энтерпрайз, либо военный корабль Клингонов некоторого типа. С каждым типом кораблей Клингонов связано время, за которое Энтерпрайз может его победить. Для спасения Энтерпрайз должен победить каждый корабль Клингонов на некотором пути к границе сетки. Ячейки считаются соседними, если у них общее ребро, но не угол (то есть четыре соседа).

Вход. Первая строка содержит количество тестов t (2 ≤ t ≤ 100). Каждый тест начинается со строки, содержащей три числа k, w и h. Число k (1 ≤ k ≤ 25) – количество различных типов военных кораблей Клингонов. Число w (2 ≤ w ≤ 100) – ширина сетки. Значение h (1 ≤ h ≤ 1000) – высота сетки.

Каждая из следующих k строк содержит заглавную латинскую букву – тип корабля Клингонов и время, необходимое Энтерпрайзу победить его. Тип корабля не может быть "E". Время задается в минутах и лежит между 0 и 100000 включительно. Все строки содержат различные типы.

Каждая из следующих h строк содержит w заглавных букв (без пробелов между ними). Среди всех h строк присутствует только одна буква "E", указывающая на местоположение Энтерпрайза; все остальные заглавные буквы – одни из k перечисленных выше, указывающих на тип военного корабля Клингонов в заданной точке.

Выход. Выведите одно целое число – время, достаточное для спасения корабля.

Пример входа	Пример выхода
2 6 3 3 A 1 B 2 C 3 D 4 F 5 G 6 ABC FEC DBG 2 6 3 A 100 B 1000 BBBBBB AAAAEB BBBBBB	2 400

РЕШЕНИЕ

алгоритм Дейкстры

Анализ алгоритма

Ячейки прямоугольной сетки будет трактовать как вершины графа. Ребра графа соединяют только соседние ячейки. При перемещении по ребру в клетку (i, j) вес его принимается равным времени, за которое Энтерпрайз сможет победить вражеский корабль, находящийся в этой клетке.

Запустим алгоритм Дейкстры (используя очередь с приоритетами) из клетки, в которой изначально находится корабль Энтерпрайз. Пусть dist[i][j] содержит наименьшее время, за которое Энтерпрайз сможет добраться до клетки (i, j). Корабль считается спасенным, если он окажется на любой клетке границы сетки. Остается вычислить минимум среди всех значений dist[i][j] для всех клеток (i, j), находящихся на границе сетки (i = 1 или i = h, j = 1 или j = w).

Реализация алгоритма

Объявим массивы, при помощи которых будем моделировать направление движения корабля по сетке. Пара (dx[i], dy[i]) для i = 0, 1, 2, 3 задает движение влево, вниз, вправо, вверх.

const int dx[] = {-1, 0, 1, 0};

const int dy[] = {0, 1, 0, -1};

Ячейка tp[c] содержит время, за которое можно победить корабль типа c.

int tp[26];

Ячейка dist[i][j] содержит наименьшее время, за которое корабль Энтерпрайз сможет добраться до клетки (i, j).

Ячейки массива mas содержат информацию о начальном состоянии кораблей на сетке: mas[i][j] содержит время, необходимое для победы над кораблем в клетке (i, j). mas[i][j] = 0, если в клетке (i, j) изначально находится Энтерпрайз.

#define MAX 1010

long long dist[MAX][MAX], mas[MAX][MAX];

Объявим структуру Node, означающую что в ячейку (i, j) можно добраться за время w.

struct Node

{

int i, j;

long long w;

Node() {}

Node(int i, int j, long long w) : i(i), j(j), w(w) {}

bool operator < (const Node& n) const

{

return (w > n.w);

}

};

Реализуем алгоритм Дейкстры с использованием очереди с приоритетами. Запускаем алгоритм из клетки (sx, sy).

void Dijkstra(int i, int j)

{

Инициализируем массив кратчайших расстояний.

memset(dist, 0x3f, sizeof(dist));

dist[sx][sy] = 0;

Положим изначально ответ равным бесконечности: res = ∞.

res = 1LL << 60;

Объявим очередь с приоритетами q и занесем в нее стартовую вершину. В ячейке (sx, sy) мы находим в момент времени 0.

priority_queue <Node> q;

q.push(Node(sx, sy, 0));

Продолжаем цикл пока очередь не окажется пустой.

while (!q.empty())

{

Извлекаем вершину Curr из очереди.

Node Curr = q.top();

q.pop();

int i = Curr.i;

int j = Curr.j;

long long weight = Curr.w;

Если вершина Curr фиктивная, то не рассматриваем ее.

if (weight > dist[i][j]) continue;

Если в очереди остались только вершины со временем, не меньшим res, то можно их не обрабатывать.

if (weight >= res) break;

Если добрались до границы сетки, то обновляем результат res.

if ((i == 1) || (i == h) || (j == 1) || (j == w))

{

if (weight < res) res = weight;

continue;

}

На данный момент в клетку (i, j) мы попали за время weight. Если мы переместимся в направлении (dx[d], dy[d]), то попадем в клетку (x, y), где x = i + dx[d], y = j + dy[d] за время weight + mas[x][y] (корабль в клетке (x, y) убивается за время mas[x][y]).

for (int d = 0; d < 4; d++)

{

int x = i + dx[d];

int y = j + dy[d];

Node next(x, y, weight + mas[x][y]);

Если указанное выше время улучшит текущее dist[x][ y], то заносим вершину next в очередь.

if (next.w < dist[x][y])

{

dist[x][y] = next.w;

q.push(next);

}

}

}

}

Основная часть программы. Читаем входные данные.

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d %d\n", &k, &w, &h);

memset(tp,0,sizeof(tp));

for(i = 0; i < k; i++)

{

Читаем типы кораблей Клингонов и время, необходимое для их уничтожения.

scanf("%c %d\n",&ch,&v);

tp[ch - 'A'] = v;

}

Читаем начальное расположение кораблей, заносим в mas[i][j] время уничтожения корабля, расположенного в клетке (i, j).

memset(dist,0x3F,sizeof(dist));

for(i = 1; i <= h; i++)

{

for(j = 1; j <= w; j++)

{

scanf("%c",&ch);

mas[i][j] = tp[ch - 'A'];

Начальные координаты Энтерпрайза занесем в (sx, sy).

if (ch == 'E') sx = i, sy = j;

}

gets(s);

}

Запускаем Дейкстру из точки (sx, sy) и выводим ответ.

Dijkstra(sx,sy);

printf("%lld\n",res);

}